#include <iostream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <vector>
/** * **/
#include <boost/dynamic_bitset.hpp>
using namespace std;
using namespace boost;
const int nn=3000;
string comment="";

int gsize;           // size of the graph      //
int m;               // length of the snake    //
bool inc[nn][nn];    // inciedence matrix      //
bool inc_tmp[nn][nn];    // inciedence matrix      //
int a[nn],c[nn];     // snake                  //
int a_tmp[nn],c_tmp[nn];     // snake                  //
int b[nn];           // degrees                //
int d[nn],f[nn];     // digits,multiplicities  //
int num;             // number for conversion  //
int trials;          // number of the trials   //
int act;             // actual num of colors   //
int opt;             // optimal coloring       //

const int mm=300;

bool allsol;         // must be set to 0 or 1   //
bool displ;          // display flag            //
bool savesol;        // solution saving flag    //
int csize,csize1;    // clique size             //
long long esize;      // number of edges         //
int prosp[mm][nn];   // the prospective nodes   //
int size[mm];        // size of prospective     //
int bound[mm];       // bounds for prosp        //
int level;           // search tree level       //
int pivot;           // pivot element           //
long long nsol;       // number of solutions     //
long long nnodes;     // number of nodes visited //
long long step;       // step size               //
long long total;      // tree size               //
long long tree[mm];   // tree                    //
int mult[mm];        // color multiplicities    //

fstream file3;

int up[nn];          // pointer for coloring    //
int addr[nn];        // pointer for coloring    //

////////////////////////////

void order()
{
    //---------------------//
    // coloring with links //
    //---------------------//

    // orders the color multiplicities //
    // orders the color classes        //
    int i,j,z,y,x,t,max,r;

    t=0;
    z=csize-level;
    x=0;
    for (i=1; i<=z; i++) {
        max=0;
        for (j=1; j<=act; j++) {
            if (max<mult[j]) {
                max=mult[j];
                r=j;
            }
        }

        x=x+max;
        y=addr[r];

        for (j=1; j<=max; j++) {
            prosp[level][++t]=a[y];
            y=up[y];
        }

        mult[r]=0;
    }

    bound[level]=x;

    for (j=1; j<=act; j++) {
        y=addr[j];
        for (i=1; i<=mult[j]; i++) {
            prosp[level][++t]=a[y];
            y=up[y];
        }
    }
}

//////////////////////////

void clique()
{
// greedy sequential clique search //
    int i,j,r,s,t,max,pivot,size;

    for (i=1; i<=m; i++) {
        b[i]=a[i];
        c[i]=0;
    }
    size=m;
    s=0;
    while (size>0) {
        max=-1;
        for (i=1; i<=size; i++) {
            t=0;
            pivot=b[i];
            for (j=1; j<=size; j++) {
                if (inc[pivot][b[j]]) {
                    t++;
                }
            }
            if (max<t) {
                max=t;
                r=i;
            }
        }
        s++;
        for (i=1; i<=m; i++) {
            if (a[i]==b[r]) {
                c[i]=s;
            }
        }
        t=0;
        pivot=b[r];
        for (i=1; i<=size; i++) {
            if (inc[pivot][b[i]]) {
                t++;
                b[t]=b[i];
            }
        }
        size=t;
    }
}

//////////////////////////////////

void degree()
{
// computes the degrees of the nodes a[1],...,a[m] //
// computes the degrees of the nodes in snake      //
    int i,j,t,x;

    for (i=1; i<=m; i++) {
        x=0;
        for (j=1; j<=m; j++) {
            if (inc[a[i]][a[j]]) {
                x++;
            }
        }
        c[i]=x;
    }

    x=1;
    i=1;
    while (x==1) {
        x=0;
        for (j=1; j<=m-i; j++) {
            if (c[j]<c[j+1]) {
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                t=c[j];
                c[j]=c[j+1];
                c[j+1]=t;
                x=1;
            }
        }
        i++;
    }
}

////////////////////////////////////

void multiplicity()
{
// orders the multiplicities of the colors //
// orders the color classes                //
    int i,j,x,y,t;

    x=act;
    for (i=1; i<=x; i++) {
        b[i]=0;
        f[i]=i;
    }
    for (i=1; i<=m; i++) {
        if (c[i]>0) {
            b[c[i]]++;
        }
    }

    y=1;
    i=1;
    while ((i<=x) && (y==1)) {
        y=0;
        for (j=1; j<=x-i; j++) {
            if (b[j]<b[j+1]) {
                t=b[j];
                b[j]=b[j+1];
                b[j+1]=t;
                t=f[j];
                f[j]=f[j+1];
                f[j+1]=t;
                y=1;
            }
        }
        i++;
    }

    for (i=1; i<=x; i++) {
        b[f[i]]=i;
    }
    for (i=1; i<=m; i++) {
        c[i]=b[c[i]];
    }

    y=1;
    i=1;
    while ((i<=m) && (y==1)) {
        y=0;
        for (j=1; j<=m-i; j++) {
            if (c[j]<c[j+1]) {
                t=c[j];
                c[j]=c[j+1];
                c[j+1]=t;
                t=a[j];
                a[j]=a[j+1];
                a[j+1]=t;
                y=1;
            }
        }
        i++;
    }
}

///////////////////////////

void coloring2()
{
// Brelaz's algorithm starting with a clique //
    int i,j,r,t,x,y;
    int max,pivot;

    act=0;
    for (i=1; i<=m; i++) {
        if (c[i]>0) {
            act++;
        }
    }
    x=1;
    while (x==1) {
        x=0;
        max=-1;
        for (i=1; i<=m; i++) {
            if (c[i]==0) {
                for (j=1; j<=act+1; j++) {
                    b[j]=0;
                }
                pivot=a[i];
                for (j=1; j<=m; j++) {
                    if (inc[pivot][a[j]]) {
                        b[c[j]]=1;
                    }
                }
                t=0;
                for (j=1; j<=act+1; j++) {
                    if (b[j]==1) {
                        t++;
                    }
                }
                if (max<t) {
                    max=t;
                    r=i;
                }
                x=1;
            }
        }
        for (j=1; j<=act+1; j++) {
            b[j]=0;
        }
        pivot=a[r];
        for (j=1; j<=m; j++) {
            if (inc[pivot][a[j]]) {
                b[c[j]]=1;
            }
        }
        j=1;
        while (b[j]==1) {
            j++;
        }
        c[r]=j;
        if (act<j) {
            act++;
        }
    }
}


void solution2()
{
// Saves solutions on the disc. //
    int i,x;

    nsol++;
    for(i=1; i<=csize; i++) {
        d[i]=prosp[i][size[i]];
        file3 << d[i] << endl;
    }
    if ( allsol==0 ) {
        level=0;
    }
}

void bogdan()
{
// greedy sequential coloring using buckets //
// implemeted by means of pointers          //
    int i,j,x,y,u,v,pivot;
    int w,t;
    bool r,s;

    x=size[level];
    act=0;
    for (u=1; u<=x; u++) {
        j=1;
        r=1;
        pivot=a[u];
        while (j<=act) {
            i=1;
            s=1;
            v=mult[j];
            y=addr[j];
            while (i<=v) {
                if (inc[pivot][a[y]]) {
                    s=0;
                    i=gsize;
                }
                i++;
                y=up[y];
            }
            if (s) {
                up[u]=addr[j];
                addr[j]=u;
                mult[j]++;
                r=0;
                j=gsize;
            }
            j++;
        }
        if (r) {
            mult[++act]=1;
            addr[act]=u;
            up[u]=0;
        }
    }
    order();
}

void progress()
{
    // Monitors the progress of the search. //
// nnodes++; //
    step++;
    total++;
    tree[level]++;
    if ( step==10000000 ) {
        nnodes++;
        step=0;
        cout << endl;
        cout << setw(10) << nnodes;
        cout << setw(10) << nsol;
        cout << setw(10) << size[1];
    }
}

void dominance()
{
// Tests dominance. //
    int i,j,x,y,z,u,v;
    bool w;

// if ( allsol==0 )
    {
        if ( 2<=level) {
            x=level-1;
            y=size[x]-size[level];
            if ( y<=5 ) {
                w=1;
                for (i=1; i<=y-2; i++) {
                    u=prosp[x][gsize+1-i+1];
                    for (j=i+1; j<=y-1; j++) {
                        v=prosp[x][gsize+1-j+1];
                        if ( inc[u][v]==1 ) {
                            w=0;
                        }
                    }
                }
                if ( w ) {
                    bound[x]=size[x]-1;
                }
            }
        }
    }
}

///////////////////////////

void repeated()
{
// colors the graph repeatedly //
    int i,j,x;

    opt=gsize;
    for (i=1; i<=trials; i++) {
        degree();
        clique();
        coloring2();
        multiplicity();
        /*cout << endl;
        cout << setw(9) << i;
        cout << setw(9) << act;
        cout << setw(9) << opt;*/

        if (act<opt) {
            for(int i=1; i<=gsize; ++i) {
                a_tmp[i]=a[i];
                c_tmp[i]=c[i];
            }
            opt=act;
        }

    }
// cout<<endl;

    for(int i=1; i<=gsize; ++i) {
        a[i]=a_tmp[i];
        c[i]=c_tmp[i];
    }
}


void test()
{
    int i,t,x,y,z,s;

    x=size[level];
    z=bound[level];
    while (x>z) {
        pivot=prosp[level][x];
        t=0;
        s=gsize+2;
        for(i=1; i<=x-1; i++) {
            y=prosp[level][i];
            if (inc[pivot][y]) {
                a[++t]=y;
            } else {
                s--;
                prosp[level+1][s]=y;
            }
        }
//progress();
        size[++level]=t;
        x=t;
        bogdan();
        z=bound[level];
        dominance();
        if (level==csize1) {
            solution2();
            x=0;
            z=0;
        }
    }
    size[level]=0;
    if (size[--level]>0) {
        size[level]--;
    }
}

//////////////////////////////

void setting()
{
    // setting the initial values //
    int i,x;

    nnodes=0;
    nsol=0;
    step=0;
    x=0;
    for (i=1; i<=m; i++) {
        prosp[1][i]=a[m-i+1];
        if (c[i]<csize) {
            x++;
        }
    }
    for(i=1; i<=csize+1; ++i) {
        size[i]=0;
        bound[i]=0;
    }
    level=1;
    size[1]=m;
// the following is a safety measure //
    size[0]=0;
    bound[1]=x;
    csize1=csize+1;
}

/////////////////////

// Greedy sequential coloring of the nodes using the      //
// Brelaz saturated coloring idea starting with a clique  //
/** * **/
bool k_clique(vector<dynamic_bitset<> > szomszedsagi, int k)
{
//==================//
//number of colorings, to find the best:
    trials=50;
//==================//
    gsize=m=szomszedsagi.size();
    csize=k;
    allsol=0;
//cout<<gsize<<m<<endl;

    int i, j;
    for(i=1; i<=m; ++i)
        for(j=1; j<=m; ++j) {
            inc[i][j]=szomszedsagi[i-1][j-1];
        }


    for(int i=1; i<=gsize; ++i) {
        a[i]=i;//gsize-i+1;
        c[i]=0;
    }
    srand(time(NULL));

    repeated();


//CP:
    setting();

// main loop for Caraghan-Pardalos//
    while( level>0 ) {
        test();
    }

    if(nsol==0) {
        return false;
    } else {
        return true;
    }
}
